package hashtable;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class 前K个高频元素_347{

    public static void main(String[] args) {
        前K个高频元素_347 solution = new 前K个高频元素_347();
        int[] ints = solution.topKFrequentFastSort(new int[]{1, 1, 1, 2, 2, 3}, 2);
        System.out.println();
    }
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> frequency = new HashMap<>();
        for(int num : nums) {
            frequency.put(num, frequency.getOrDefault(num, 0) + 1);
        }
        //按照频率来的小顶堆  PriorityQueue无法实现定长  需要自行判断
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        for(Map.Entry<Integer, Integer> entry : frequency.entrySet()) {
            if(queue.size() == k) {
                if(queue.peek()[1] >= entry.getValue()) {
                    continue;
                }
                queue.poll();
            }
            queue.offer(new int[]{entry.getKey(), entry.getValue()});
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll()[0];
        }
        return res;
    }

    /**
     * 快排方式找k位置 注意不是完全排序 只找前大后小的第k位置的方法
     */
    public int[] topKFrequentFastSort(int[] nums, int k) {
        Map<Integer, Integer> frequency = new HashMap<>(nums.length);
        for(int num : nums) {
            frequency.put(num, frequency.getOrDefault(num, 0) + 1);
        }
        int[][] fArr = new int[frequency.size()][2];
        int i = 0;
        for(Map.Entry<Integer, Integer> entry : frequency.entrySet()) {
            fArr[i][0] = entry.getKey();
            fArr[i][1] = entry.getValue();
            i ++;
        }

        return findTopK(fArr, k, 0, fArr.length - 1);
    }

    // 题中快排只考虑找pivot基准位置 并不是完全的快排
    private int[] findTopK(int[][] arr, int k, int low, int high) {
        int pivot = low + (int) (Math.random() * (high - low + 1)); // 注意  这里要加上起始坐标low
        swap(arr, pivot, low); // 交换low和随机下标
        int i = low, base = arr[low][1]; // 以low的frequency为基准  进行倒序快排
        for (int j = low + 1; j <= high; j++) {  // 因为 low、high 都是具体坐标  因此  j可以等于high
            if(arr[j][1] > base ) {
                swap(arr,  ++ i, j); // 交换 i 的下一个元素 和j 保证从low的下一个开始 都是大于base的
            }
        }
        swap(arr, low, i);
        if(i == k - 1) {
            int[] topK = new int[k];
            for(int f = 0; f < k; f++) {
                topK[f] = arr[f][0];
            }
            return topK;
        } else if( i > k - 1) {
            return findTopK(arr, k, low, i - 1 );
        } else {
            return findTopK(arr, k, i + 1, high );
        }

    }

    /**
     * 二维数组交换
     */
    private void swap(int[][] arr, int pivot, int low) {
        if(pivot == low) return;
        int[] tmp = arr[pivot];
        arr[pivot] = arr[low];
        arr[low] = tmp;
    }
}
